package 随机选择算法;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/11/20
 */
// 无序数组中第K大的元素
// 测试链接 : https://leetcode.cn/problems/kth-largest-element-in-an-array/
public class RandomizedSelect {
    // 随机选择算法，时间复杂度O(n)
    public int findKthLargest(int[] nums, int k) {
        return randomizedSelect(nums, nums.length-k);
    }

    // 如果arr排序的话，在i位置的数字是什么
    public static int randomizedSelect(int[] arr, int i){
        int ans = 0;
        for(int l = 0, r = arr.length-1; l <= r; ){
            // 随机这一下，常数时间比较大
            // 但只有这一下随机，才能在概率上把时间复杂度收敛到O(n)
            int x = arr[l + (int)(Math.random()*(r-l+1))];
            partition(arr, l, r, x);
            // 因为左右两侧只需要走一侧
            // 所以不需要临时变量记录全局的first、last
            // 直接用即可
            if(first > i){
                r = first-1;
            }else if(last < i){
                l = last+1;
            }else{
                ans = arr[i];
                break;
            }
        }
        return ans;
    }

    // 荷兰国旗问题
    public static int first, last;
    public static void partition(int[] arr, int l, int r, int x){
        first = l;
        last = r;
        int i = l;
        while(i <= last){
            if(arr[i] == x){
                i++;
            }else if(arr[i] < x){
                swap(arr, first++, i++);
            }else{
                swap(arr, i, last--);
            }
        }
    }

    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
